package cykbt.core;

public class CYK {
	protected ChomskyGrammar cg;

	public CYK(ChomskyGrammar cg) {
		this.cg = cg;
	}

	public boolean solve(String word) {
		if (word.isEmpty())
			return false;
		Cell[][] cells = this.createTable(word.length());
		for (int i = 0; i < cells[0].length; i++) {
			cells[0][i].add(cg.getSymbolsThatCanDeriveTo(word.charAt(i)));
		}
		// showCells(cells[0]);
		for (int l = 1; l < cells.length; l++) {
			for (int i = 0; i < cells.length - l; i++) {
				for (int m = 0; m < l; m++) {
					cells[l][i].add(cg.getSymbolsThatCanDeriveTo(cells[m][i],
							cells[l - m - 1][i + m + 1]));
				}
			}
			// showCells(cells[l]);
		}
		return cells[cells.length - 1][0].isFinal(cg);
	}

	protected Cell[][] createTable(int size) {
		Cell[][] cells = new Cell[size][];
		for (int i = 0; i < cells.length; i++) {
			cells[i] = new Cell[size - i];
			for (int j = 0; j < cells[i].length; j++) {
				cells[i][j] = new Cell();
			}
		}
		return cells;
	}

	/*
	 * Debug function
	 * 
	 * private void showCells(Cell[] cellules) { for (Cell cellule : cellules) {
	 * System.out.print(cellule); } System.out.println(); }
	 */

}
